/**
 * 试编写带头结点的单链表L中删除一个最小值结点的高效算法
 */
#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
	int data;
	struct LNode* next;
} LNode,*LinkedList;

//单链表带头结点初始化
bool init(LinkedList& list);

//单链表插入
bool insert(LinkedList &list, int data);

//链表元素展示
void print(LinkedList &list);

//删除链表中最小值
bool deleteNode(LinkedList &list);

int main()
{
	LinkedList list=NULL;
	init(list);	
	insert(list,8);
	insert(list,7);
	insert(list,9);
	insert(list,5);	
	insert(list,2);
	insert(list,5);
	printf("删除前:\t");
	print(list);
	printf("\n删除后:\t");
	deleteNode(list);
	print(list);
	return 0;
}

bool init(LinkedList& list)
{
	LNode* node=(LNode* )malloc(sizeof(LNode));
	if(!node) return false;
	node->data=-1;
	node->next=NULL;
	list=node;
	return true;
}

bool insert(LinkedList &list, int data)
{
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	newNode->data=data;
	LNode* node=list;

	while(node->next) node=node->next;
	node->next=newNode;
	return true;
}

void print(LinkedList &list)
{
	LNode* node=list;
	while(node)
	{
		printf("%d ",node->data);
		node=node->next;
	}
	printf("\n");
}

bool deleteNode(LinkedList &list)
{
	LinkedList node=list->next;	//定义一个遍历结点
	//只有一个头结点
	if(!node->next) return false;

	LNode* pre_node=list;	//pre_node指向node的前驱结点:pre_node->next=node;
	LNode* min_node=node;	//用于存放最小值域的结点,默认指向第一个元素的结点
	LNode* min_pre_node=pre_node;	//最小结点的前驱节点, min_pre_node->next=min_node
	while(node)
	{	
		if(node->data<min_node->data)
		{
			min_node=node;
			min_pre_node=pre_node;
		}
		pre_node=node;
		node=node->next;
	}
	//删除最小结点以及修改最小结点的前驱结点的指向
	min_pre_node->next=min_node->next;
	free(min_node);
	return true;
}